package com.gagakuai.concurrent.locks;

import java.io.Serializable;
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.Date;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.LockSupport;

/*
 * @program: settement
 * @description: 抽象队列同步器
 * @author: houhong
 * @create: 2022-11-16 23:04
 */
public abstract class AbstactQueuedSychronier extends AbstractOwnableSynchronizer implements Serializable {

    // 自旋超时时间
    static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L;

    /*
     *   transient修饰符用于类属性、变量，表示该类的序列化过程在为该类的任何实例创建持久字节流时应该忽略此类变量。
     *
     *   transient使用场景：
     * 在类实现序列化接口，而类下某个变量不想被序列化的情况下，用transient修饰该变量，可避免该变量被序列化。
     *
     * */

    /*
     * 抽象队列同步器特别依赖于状态 来实现互斥性
     */
    private transient volatile int state = 0;

    /*
     * 定义出队节点
     */
    private transient volatile Node head;
    /*
     * 定义入队节点
     */
    private transient volatile Node tail;

    private static final VarHandle STATE;
    private static final VarHandle HEAD;
    private static final VarHandle TAIL;

    static {
        MethodHandles.Lookup lookup = MethodHandles.lookup();
        try {
            STATE = lookup.findVarHandle(AbstactQueuedSychronier.class, "state", int.class);
            HEAD = lookup.findVarHandle(AbstactQueuedSychronier.class, "head", Node.class);
            TAIL = lookup.findVarHandle(AbstactQueuedSychronier.class, "tail", Node.class);
        } catch (ReflectiveOperationException e) {
            throw new ExceptionInInitializerError(e);
        }

    }


    protected AbstactQueuedSychronier() {
    }

    public final int getState() {
        return state;
    }

    public final void setState(int state) {
        STATE.compareAndSet(this, 0, state);
    }

    /*============独占锁==================*/


    /*
     * @param arg
     * @return
     * @Author houhong
     * @Description //TODO 申请独占锁，允许阻塞带有中断标记的线程
     * @Date 7:32 下午 2022/11/19
     */
    public final void acquire(int arg) {

        // 尝试获取独占锁,获取失败
        if (!tryAcquire(arg)) {
            /*
             *  当前线程没有获取到锁，
             *   然后把其封装成Node 放入CHL队列中去排队，线程是否需要阻塞？
             */
            Node node = addWaiter(Node.EXCLUSIVE);

            /*
             * 在线程进入CHL排队后 会再尝试一次获取锁，以免这时候，其他线程释放锁了，当前线程还在排队
             */
            if (acquireQueued(node, arg)) {
                // 代码走到这里来 表示这里已经被唤醒了，且有中断标记，这里需要再设置
                selfInterrupt();
            }

        }
    }

    /*
     * @param arg
     * @return
     * @Author houhong
     * @Description //TODO 申请独占式的获取锁  不允许阻塞带有中标记的线程
     * @Date 9:30 下午 2022/11/19
     */
    public final void acquireInterruptibly(int arg) throws InterruptedException {

        if (Thread.interrupted()) {
            throw new InterruptedException();
        }

        // 尝试抢锁
        if (!tryAcquire(arg)) {
            // 抢锁失败后阻塞
            doAcquireInterruptibly(arg);
        }
    }

    /*
     * 申请共享锁，允许带有中断标记的阻塞线程
     */
    public final void acquireShared(int arg) {

        if (tryAcquiredShared(arg) < 0) {
            doAcquireShared(arg);
        }

    }

    /*
     * 当node进入排队后再次尝试申请锁，如果还是失败，则可能进入阻塞
     */
    public void doAcquireShared(int arg) {

        // 向CHL队列中添加一个共享模式的Node 进行排队
        final Node node = addWaiter(Node.SHARED);
        //记录当前节点从阻塞醒来的状态
        boolean interrupted = false;

        // skin
        for (; ; ) {
            //前驱
            final Node predecessor = node.predecessor();
            if (predecessor == head) {

                //这里r是表示是否获取成功了 r>0 成功
                int r = tryAcquiredShared(arg);

                if (r >= 0) {

                    setHeadAndPropagate(node, r);


                    predecessor.next = null;
                }
            }

        }

    }

    /*
     * 更新头节点为node ,并设置其模式为propate 广播模式
     * 唤醒其后继节点
     */
    public void setHeadAndPropagate(Node node, int propate) {
        // 记录旧的头节点
        Node h = head;
        //将当前节点设置为头节点，舍弃原来的头节点
        setHeader(node);


        // propate > 0 表示还有许可证，抢锁成功
        if (propate > 0
                || h == null || h.waitStatus < 0 || (h = head) == null || h.waitStatus < 0) {

            Node s = node.next;
            if (s == null || s.isShared()) {
                // 为共享结点设置Node.PROPAGATE标记，或唤醒其下一个结点
                doReleaseShared();
            }
        }


    }


    /*
     * @param nanosTimeout
     * @param arg
     * @return {@link boolean}
     * @Author houhong
     * @Description //TODO 申请独占锁，(不允许带有中断)一次失败后 带着超时标记继续申请
     * @Date 9:41 下午 2022/11/19
     */
    public final boolean tryAcquireNancos(int arg, long nanosTimeout) throws InterruptedException {

        // 测试当前线程是否已经中断，线程的中断状态会被清除
        if (Thread.interrupted()) {
            throw new InterruptedException();
        }

        // 申请一次锁
        return tryAcquire(arg)
                || doAcquireNanos(arg, nanosTimeout);
    }

    /*
     * 申请独占锁，带有超时标记
     * 1： 如果nanosTimeout <= 1000  则一直不断尝试获取
     * 2： nanosTimeout > 1000 则线程抢锁失败后，会进入阻塞（累计阻塞时长不超过nanosTimeout纳秒）
     * * 阻塞可能中途被唤醒，也可能自然醒来
     * * 不管哪种方式醒来的，只要醒来就再次尝试获取锁
     * * 如果是中途醒来的，且获取锁失败，那么会继续阻塞剩余的时长，直至超时
     * * 如果是自然醒来的，且抢锁失败，那么说明已经超时了
     * * 只要到了超时，则需要取消任务，并返回fasle，代表抢锁失败
     */
    private final boolean doAcquireNanos(int arg, long nanosTimeout) throws InterruptedException {

        if (nanosTimeout <= 0L) {
            return false;
        }
        // 结束时间
        final long deadTime = System.nanoTime() + nanosTimeout;


        final Node node = addWaiter(Node.EXCLUSIVE);

        try {
            for (; ; ) {

                final Node predecessor = node.predecessor();
                if (predecessor == head) {

                    if (tryAcquire(arg)) {
                        setHeader(head);
                        predecessor.next = null;
                        return true;
                    }
                }

                //判断是否超时
                nanosTimeout = deadTime - System.nanoTime();
                //已经超时 则需要取消任务，并返回fasle，代表抢锁失败
                if (nanosTimeout <= 0L) {
                    cancelAcquire(node);
                    return false;
                }

                if (shouldParkAfterAcquireFailed(predecessor, node)) {

                    if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) {
                        // 使线程阻塞nanosTimeout（单位：纳秒）时长后自动醒来（中途可被唤醒）
                        LockSupport.parkNanos(this, nanosTimeout);
                    }
                    //测试当前线程是否已经中断，线程的中断状态会被清除
                    if (Thread.interrupted()) {
                        throw new InterruptedException();
                    }
                }
            }
        } catch (Throwable t) {

            // 如果中途有异常发生，应当撤销当前线程对锁的申请
            cancelAcquire(node);
            throw t;
        }
    }

    /*
     * 抢锁失败后，尝试阻塞线程
     */
    private void doAcquireInterruptibly(int arg) throws InterruptedException {

        Node node = addWaiter(Node.EXCLUSIVE);

        try {
            for (; ; ) {

                final Node predecessor = node.predecessor();

                if (head == predecessor) {

                    if (tryAcquire(arg)) {
                        setHeader(node);
                        predecessor.next = null;
                        return;
                    }
                }

                if (shouldParkAfterAcquireFailed(predecessor, node)) {

                    if (parkAndCheckInterrupt()) {
                        throw new InterruptedException();
                    }
                }
            }
        } catch (Throwable t) {
            cancelAcquire(node);
            throw t;
        }
    }

    /*
     * 在Node 进入线程以后 会再次尝试获取锁，
     * 失败后会可能会阻塞Node
     */
    final boolean acquireQueued(Node node, int arg) {

        // 记录当前线程从阻塞中醒来的时候的中断标记
        boolean interrupted = false;

        /*
         *  自旋，成功申请到锁后退出
         *    1：每个陷入阻塞的线程在醒来后，都会重新去获取锁，
         *    2： 只有当前Node 排在队首的时候，才能够去竞争锁
         *    3： 锁申请成功后，需要丢弃头节点，让自己成为头节点
         *
         */
        try {
            for (; ; ) {
                // 当前节点的前驱
                final Node predecessor = node.predecessor();

                // 当前节点在CHL队首
                if (predecessor == head) {
                    //再次尝试申请锁
                    if (tryAcquire(arg)) {
                        setHeader(node);
                        // 切断旧的头结点与后一个结点的联系，以便GC
                        predecessor.next = null;

                        // 返回线程当前的中断标记（如果线程在阻塞期间被标记为中断，这里会返回true）
                        return interrupted;
                    }
                }
                /*
                 *  抢锁失败后，应该让当前线程阻塞，等待他的前驱节点释放掉锁以后
                 *  由前驱节点去唤醒当前节点 基于这种考虑
                 *  尝试为node的前驱设置阻塞标记（每个结点的阻塞标记设置在其前驱上）
                 */
                if (shouldParkAfterAcquireFailed(predecessor, node)) {

                    /*
                     *  使线程陷入阻塞
                     *
                     *     1：如果首次到达这里的时候。线程被标记为中断，这里只是简单的清除 中断
                     *      并且 返回true; 接下来 第二次循环会走到这里来，便park住线程
                     *     2:  如果首次来到这里的时候，没有被标记为中断，则直接park
                     *      当线程被唤醒后，返回线程当前的中断标记（阻塞(park)期间也可设置中断标记）
                     *
                     *    |=  两个二进制对应位为0时该位为0，否则为1  ( 0== false ,1== true)
                     *     010 0
                     *     011 0
                     *  =  011 0
                     */
                    interrupted |= parkAndCheckInterrupt();
                }
            }
        } catch (Throwable t) {

            //如果中途发生异常，需要撤销当前线程申请锁   需要设置为cannecled 状态
            cancelAcquire(node);

            if (interrupted) {
                selfInterrupt();
            }
            throw t;
        }

    }

    /*
     * 为线程设置中断标记
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /*
     * 设置当前node 状态为CANNECLED 状态 // TODO: 2022/11/19
     */
    private final void cancelAcquire(Node node) {

        if (node == null) {
            return;
        }
        //删除对线程的饮用
        node.thread = null;
        //当前节点的前驱节点
        Node pred = node.prev;
        // 顺着node的前驱向前遍历，将标记为取消的node结点连成一片
        while (pred.waitStatus > 0) {
            node.prev = pred = pred.prev;
        }
        Node preNext = pred.next;
        // 设置节点状态
        node.waitStatus = Node.CANCELLED;

        // 当前节点如果是最后一个节点的场景，需要把当前节点的前驱节点设置为tail 节点
        if (node == tail && compareAndSetTail(node, pred)) {
            //将当前节点的前驱节点的后继节点设置为null;
            pred.compareAndSetNext(preNext, null);
        } else {

            int ws;

            // 当 [当前]的前驱节点不是头节点的时候，并且 在前驱节点的状态是SIGAL的时候需要获取所有阻塞的线程
            if (pred != head
                    && ((ws = pred.waitStatus) == Node.SIGNAL ||
                    (ws <= 0 && pred.compareAndSetWaitStatus(ws, Node.SIGNAL)))
                    && pred.thread != null) {

                // 将处于阻塞状态的node连成一片，通过后继向后遍历即可获得
                Node next = node.next;
                if (next != null && next.waitStatus <= 0) {
                    pred.compareAndSetNext(preNext, next);
                }
            } else {
                // 否则需要唤醒后继节点
                unparkSuccessor(node);
            }
            // 将节点从CHL队列中脱离处理，以便于GC
            node.next = node;
        }
    }

    /*
     * 阻塞线程，并且清除线程的中断状态，返回值表示之前线程的中断状态
     */
    private final boolean parkAndCheckInterrupt() {

        /*
         *  阻塞当前线程，但是对于设置了中断的线程无效
         */
        LockSupport.park(this);
        return Thread.interrupted();
    }

    /*
     * @param node 当前节点
     * @param p    当前节点的前驱节点
     * @Description //TODO  尝试为node的前驱设置阻塞标记（每个结点的阻塞标记设置在其前驱上）
     * @Date 8:36 下午 2022/11/19
     */
    private static boolean shouldParkAfterAcquireFailed(Node p, Node node) {

        // node 前驱节点的状态
        int ws = p.waitStatus;

        if (ws == node.SIGNAL) {
            return true;
        }
        // 为cancelled 状态 则顺着其前驱向前遍历，将紧邻的待取消结点连成一片
        if (ws > 0) {
            do {
                node.prev = p = p.prev;
            } while (p.waitStatus > 0);

            p.next = node;
        } else {

            // 更新Node 前驱节点的状态为SIGNAL，并且阻塞当前Node
            p.compareAndSetWaitStatus(ws, Node.SIGNAL);

        }
        return false;
    }

    /*
     * 设置当前节点为head 节点，丢弃原来的头节点
     */
    private final void setHeader(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }

    /*
     * @param mode
     * @return {@link Node}
     * @Author houhong
     * @Description //TODO 将线程封装成Node然后放入CHL队列中进行排队
     * @Date 7:38 下午 2022/11/19
     */
    private Node addWaiter(Node mode) {

        Node node = new Node(mode);
        //采用cas 放入到CHL队列的队尾
        enq(node);
        return node;
    }

    /*
     * @param node
     * @return {@link Node}
     * @Description //TODO 尾插入CHL需要保证并发入队
     */
    private Node enq(Node node) {

        for (; ; ) {

            //记录指向队尾的指针
            Node oilTail = tail;
            if (oilTail != null) {
                // 设置当前的节点的前驱节点为原来尾节点
                node.setPrevRelaxed(oilTail);
                //更新tail 指针 保证线程安全
                if (compareAndSetTail(oilTail, node)) {
                    oilTail.next = node;
                    return oilTail;
                }

            } else {
                //还不存在CHL队列，需要初始化一个队列
                initializeSyncQueue();
            }

        }

    }

    /*
     * @Author houhong
     * @Description //TODO   同步队列不存在，初始化一个CHL队列的头节点，并且设置head 和tail指针
     * @Date 7:46 下午 2022/11/19
     */
    private final void initializeSyncQueue() {
        Node h;
        if (HEAD.compareAndSet(this, null, (h = new Node()))) {
            tail = h;
        }
    }


    /*
     * @param arg
     * @return {@link boolean}
     * @Author houhong
     * @Description //TODO 尝试获取一次独占锁,具体实现交给子类
     * @Date 7:35 下午 2022/11/19
     */
    protected boolean tryAcquire(int arg) {

        throw new UnsupportedOperationException();
    }

    protected final boolean compareAndSetTail(Node expect, Node update) {

        return TAIL.compareAndSet(this, expect, update);

    }

    /*
     * 判断当前锁是否是当前线程的持有者
     */
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    public final boolean compareAndSetState(int expect, int update) {
        return STATE.compareAndSet(this, expect, update);
    }

    /*
     * 判断CHL 队列里面的队头是否还有除了当前线程以外的线程在排队
     * ture = 有 fasle = 没有
     */
    public final boolean hasQueuedPredecessors() {

        Node h, s;

        if ((h = head) != null) {

            // 头节点的后继节点为空 或者在当前的CHL节店处于异常状态，需要不能从头去遍历了，需要从尾节点去遍历，有可能是发生异常？ 还是因为放在了条件队列？ 导致头节点没有串联上？
            if ((s = h.next) == null || s.waitStatus > 0) {
                s = null;
                //从队尾去遍历CHL 队列
                for (Node p = tail; p != h && p != null; p = p.prev) {
                    // 节点处于阻塞 等待被前驱节点唤醒的状态
                    if (p.waitStatus <= 0) {
                        s = p;
                    }
                }
            }

            //存在CHL队列 如果只有头节点
            return s != null && s.thread != Thread.currentThread();
        }
        //不存在CHL队列
        return false;

    }

    /*====================申请锁结束=============================*/

    /*====================释放锁开始====================================*/

    /*
     * @param arg 参数
     * @return {@link boolean}
     * @Author houhong
     * @Description //TODO 释放锁 如果锁已被完全释放，则唤醒后续的阻塞线程。返回值表示本次操作后锁是否自由
     * @Date 10:06 下午 2022/11/19
     */
    public final boolean release(int arg) {
        // 释放一次锁，返回值表示同步锁是否处于自由状态（无线程持有）
        if (tryRelease(arg)) {
            //代码走到这里来 表示 已经处于自由状态 需要唤醒后继节点
            Node h = head;
            if (h != null && h.waitStatus != 0) {
                unparkSuccessor(h);
            }

            return true;
        }

        return false;
    }

    /*
     * @param node
     * @return
     * @Author houhong
     * @Description //TODO  唤醒后继节点 这里需要注意一个细节： 再这里的时候，如果是waitStatus == CANNELLED 的不需要 =唤醒
     * @Date 10:14 下午 2022/11/19
     */
    private final void unparkSuccessor(Node node) {

        int ws = node.waitStatus;
        if (ws < 0) {
            node.compareAndSetWaitStatus(ws, 0);
        }

        Node s = node.next;
        /*
         * 如果s==null，说明node已经是尾结点，后面没有需要唤醒的结点了
         *
         * 如果s!=null，且s.waitStatus>0，说明node被标记为Node.CANCELLED（取消）
         * 此时，需要从尾端向前遍历，找到离s最近的正处于阻塞的后继，以便后续唤醒它
         */
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node p = tail; p != node && p != null; p = p.prev) {
                if (p.waitStatus <= 0) {
                    s = p;
                }
            }
        }

        //唤醒 后继节点
        if (s != null) {
            LockSupport.unpark(s.thread);
        }


    }

    /*
     * // TODO: 2022/11/19
     * 释放一次锁，返回值表示同步锁是否处于自由状态，由子类实现
     * true == 是自由状态  false 表示非
     */
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    /*==================共享锁=======================*/


    /*
     * 尝试申请共享锁，具体行为由子类完成
     */
    protected int tryAcquiredShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /*
     * @param arg
     * @return
     * @Author houhong
     * @Description //TODO 申请共享锁，不允许阻塞带有中断标记的线程
     * @Date 12:46 上午 2022/11/21
     */
    public final void acquireSharedInterruptibly(int arg) throws InterruptedException {

        //如果当前线程已经被中断，那么这个Api 会清除中断
        if (Thread.interrupted()) {
            throw new InterruptedException();
        }
        // 尝试共享性的获取锁，获取失败后，需要入队，一个钩子方法，交给子类完成
        if (tryAcquiredShared(arg) < 0) {

            doAcquireSharedInterruptibly(arg);
        }
    }

    /*
     * 抢锁失败后，尝试将其阻塞
     */
    private void doAcquireSharedInterruptibly(int arg) throws InterruptedException {

        final Node node = addWaiter(Node.SHARED);
        try {
            for (; ; ) {
                final Node predecessor = node.predecessor();
                if (predecessor == head) {

                    int r = tryAcquiredShared(arg);
                    //获取锁成功，需要将node设置为head
                    if (r >= 0) {
                        //更新头节点，并且设置其为Node.propagate 或者唤醒后继节点
                        setHeadAndPropagate(node, r);
                        // 使得前驱为null 方便gc
                        predecessor.next = null;
                        return;
                    }

                    // 抢锁失败时，尝试为node的前驱设置阻塞标记（每个结点的阻塞标记设置在其前驱上）
                    if (shouldParkAfterAcquireFailed(predecessor, node)) {
                        // 设置当前线程进入阻塞状态，并清除当前线程的中断状态
                        if (parkAndCheckInterrupt()) {
                            // 如果线程被唤醒时拥有中断标记（在阻塞期间设置的），这里抛出异常
                            throw new InterruptedException();
                        }
                    }
                }
            }

        } catch (Throwable t) {
            // 如果中途有异常发生，应当撤销当前线程对锁的申请
            cancelAcquire(node);
            throw t;
        }
    }

    /*
     * @param arg
     * @return {@link boolean}
     * @Author houhong
     * @Description //TODO 释放共享锁
     * @Date 12:55 上午 2022/11/21
     */
    public final boolean releaseShared(int arg) {

        // 尝试共享的释放锁
        if (tryReleaseShared(arg)) {
            //唤醒下一个节点
            doReleaseShared();
            return true;
        }
        return false;
    }

    /*
     * 钩子方法，交给子类完成
     */
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /*
     * 释放锁，并唤醒排队的节点
     */
    private void doReleaseShared() {

        for (; ; ) {

            Node h = head;

            if (h != null && h != tail) {
                //头节点状态
                int ws = h.waitStatus;
                //需要唤醒后继节点
                if (ws == h.SIGNAL) {

                    if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0)) {
                        continue;
                    }

                    unparkSuccessor(h);
                } else {

                    //  尝试设置Node.PROPAGATE标记
                    if (ws == 0) {
                        if (!h.compareAndSetWaitStatus(0, Node.PROPAGATE)) {
                            continue;
                        }
                    }
                }
            }

            if (h == head) {
                break;
            }


        }
    }

    /*
     * 队列节点
     */
    final static class Node {

        /*
         * 当前节点的类型
         */
        static final Node EXCLUSIVE = null;
        /*
         * 共享
         */
        static final Node SHARED = new Node();

        /*
         * 当前节点的状态
         */
        volatile int waitStatus;
        /*
         * 当前节点所持有的线程
         */
        volatile Thread thread;

        volatile Node prev;

        volatile Node next;

        /*
         * 条件队列的下一个等待者
         */
        volatile Node nextWaiter;

        /*
         *  取消线程，当前线程在阻塞期间发生了异常
         *  那么需要设置该线程为 【取消状态】表示 不再进入CHl】队列
         */
        static final int CANCELLED = 1;

        /*
         * 该标记指示一个节点在等待一个信号，即这指示一个节点正处于被阻塞中，发出此信号后，就可以唤醒
         * 即：如果一个Node处于阻塞状态，那么会在他的【前驱】节点设置一个SIGNAL 标记；
         * 每个处于阻塞并且即将执行的节点 一定位于头节点之后（不考虑插队，并且该头节点设置了SIGNAL标记的
         * 这么涉及的目的是：
         * 只需要通过同节点的SIGAL 标记就可以去唤醒下一个需要竞争的线程
         */
        static final int SIGNAL = -1;

        /*
         *  仅仅用于【条件队列】节点的状态码
         *
         *  该标记意味着此节点 正位于 【条件队列】中，
         *   且该节点所包含的线程被暂时阻塞，稍后被唤醒后会被放入到【同步队列】中 继续执行等待操作
         *
         *
         */
        static final int CONDITION = -2;

        /*
         * 该标记指示结点已经位于同步队列之外
         * 当一个共享结点没有经过阻塞就直接获取锁时，
         * 会将头结点更新为该结点，并且为该结点设置PROPAGATE标记，
         * 接下来，如果其后续结点也不需要经过阻塞，那么该结点保持PROPAGATE标记，
         * 反之，如果其后续结点需要经过阻塞，那么该标记会被修改为SIGNAL
         */
        static final int PROPAGATE = -3;


        private static final VarHandle WAITSTATUS;  // 保存字段 waitStatus 的内存地址
        private static final VarHandle PREV;        // 保存字段 prev       的内存地址
        private static final VarHandle NEXT;        // 保存字段 next       的内存地址
        private static final VarHandle THREAD;      // 保存字段 thread     的内存地址

        // 获取字段地址
        static {
            try {
                MethodHandles.Lookup l = MethodHandles.lookup();
                WAITSTATUS = l.findVarHandle(Node.class, "waitStatus", int.class);
                PREV = l.findVarHandle(Node.class, "prev", Node.class);
                NEXT = l.findVarHandle(Node.class, "next", Node.class);
                THREAD = l.findVarHandle(Node.class, "thread", Thread.class);
            } catch (ReflectiveOperationException e) {
                throw new ExceptionInInitializerError(e);
            }

            Class<?> ensureLoaded = LockSupport.class;
        }

        /*
         * 定义一个空节点，作为头节点/共享标记
         */
        public Node() {
        }

        /*
         * 创建一个共享/独占模式的node
         */
        public Node(Node nextWaiter) {
            this.nextWaiter = nextWaiter;
            this.thread = Thread.currentThread();
        }

        /*
         * 创建一个状态为waitStatus 的节点
         */
        public Node(int waitStatus) {
            WAITSTATUS.set(this, waitStatus);
            THREAD.set(this, Thread.currentThread());
        }

        /*
         * 获取前驱节点
         */
        final Node predecessor() {

            Node p = prev;
            if (p == null) {
                throw new NullPointerException();
            }
            return p;

        }

        /*
         * 设置当前节点的prev 为P
         */
        private final void setPrevRelaxed(Node p) {
            PREV.set(this, p);
        }

        /*
         * 是否为共享节点
         */
        final boolean isShared() {
            return nextWaiter == SHARED;
        }


        /*
         * @param uodate
         * @param expect
         * @return {@link boolean}
         * @Description //TODO cas设置当前节点waitStatus
         * @Date 8:55 下午 2022/11/19
         */
        final boolean compareAndSetWaitStatus(int expect, int uodate) {
            return WAITSTATUS.compareAndSet(this, expect, uodate);
        }

        final boolean compareAndSetNext(Node expect, Node update) {
            return NEXT.compareAndSet(this, expect, update);
        }
    }




    /*==============================================条件队列==========================================*/


    /*
     * 条件队列 对象  用于更精准的指导线程的同步行为
     */
    public class ConditionObject implements Condition, Serializable {

        private static final long serialVersionUID = 5363868799534658563L;


        /*
         * 刚刚唤醒的线程带有中断标记，且该线程node仍在【|条件队列|】，此时需要为线程恢复中断标记
         */
        private static final int REINTERRUPT = 1;
        /*
         * 刚刚唤醒的线程带有中断标记，且该线程node已进入了【|同步队列|】，此时需要抛出异常
         */
        private static final int THROW_IE = -1;
        /*
         * 条件队列 是以单链表的形式组织的，firstWaiter和lastWaiter是首尾结点,不存在头节点
         */
        private transient Node firstWaiter, lastwaiter;


        public ConditionObject() {
        }



        /*▼ 暂时阻塞 ████████████████████████████████████████████████████████████████████████████████┓ */


        /*
         * 使当前的活跃线程阻塞，送入到[条件队列] 中进行排队，并且 唤醒 [CHL队列]中的等待者
         *
         *
         */
        @Override
        public void awaitUninterruptibly() {

        }

        /*
         * 使当前活跃的线程暂时陷入阻塞，进入【|条件队列|】排队，并唤醒【|同步队列|】中的等待者...
         * 直到收到signal()命令，该线程才恢复运行
         *
         * 禁止阻塞带有中断标记的线程
         *
         * 操作步骤：
         * 1.将该线程的引用封装到{条件node}中，并进入【|条件队列|】排队
         * 2.释放掉该线程持有的全部许可证，即让锁重新处于可用状态
         * 3.唤醒【|同步队列|】中的等待者重新争锁
         * 4.将自身陷入阻塞，等待signal()唤醒
         * 5.被signal()唤醒后，将排队的{条件node}移入【|同步队列|】，
         *   并恢复其许可证，让其继续执行...
         */
        @Override
        public void await() throws InterruptedException {
            // 如果线程带有中断标记，则抛出异常
            if (Thread.interrupted()) {
                throw new InterruptedException();
            }

            //将当前线程引入到条件队列中
            Node node = addConditionWaiter();


            /*
             * 针对独占锁，丢弃node所在线程持有的所有许可证（数量由savedState保存），并唤醒【|同步队列|】后续的阻塞线程
             * 这样一来，同步队列中排在首位的线程又可以开始抢锁了
             */
            int savedState = fullyRelease(node);

            int interruptMode = 0;


            // 判断node是否正位于【|同步队列|】中等待重新获取锁
            while (!isOnSyncQueue(node)) {

                // 如果结点位于【|条件队列|】，则暂停运行，陷入阻塞
                LockSupport.park(this);

                /* 从这里被signal()唤醒后，node已成为【|同步队列|】的首个结点（不是头结点），并准备去抢锁 */
                // 唤醒阻塞线程后，首先检查其当前是否有中断标记，如果有的话直接跳出循环
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) {
                    break;
                }
            }


            /*
             * 之前被阻塞的线程现在已经可以去争锁了
             * 而且，争锁时会携带之前保存的许可证数量
             * 争锁成功后，该结点会成为【|同步队列|】的头结点，并恢复运行
             */
            if (acquireQueued(node, savedState)) {

                // 如果不需要抛异常，则修改标记为REINTERRUPT，代表稍后要恢复线程的中断状态
                if (interruptMode != THROW_IE) {
                    interruptMode = REINTERRUPT;
                }
            }

            //从条件队列中清除
            if (node.nextWaiter != null) {
                unlinkCancelledWaiters();
            }

            // 有中断标记的情况下
            if (interruptMode != 0) {
                // 对刚刚唤醒的带有中断标记的线程进行特殊处理
                reportInterruptAfterWait(interruptMode);
            }


        }

        /*
         * 使当前活跃的线程暂时陷入阻塞，进入【|条件队列|】排队，并唤醒【|同步队列|】中的等待者...
         * 直到收到signal()的信号，或超时醒来，该线程才恢复运行
         *
         * 禁止阻塞带有中断标记的线程
         *
         * nanosTimeout是相对时间，代表最长阻塞时间，过了这个时间，即使没有收到signal()的信号，也会自己醒来
         */
        @Override
        public long awaitNaos(long nanosTimeout) throws InterruptedException {
            // 如果线程带有中断标记，则抛出异常
            if (Thread.interrupted()) {
                throw new InterruptedException();
            }


            // 结束时间
            final long deadTime = System.nanoTime() + nanosTimeout;

            long initialNanos = nanosTimeout;

            //添加一个新的【条件节点】到【条件队列】中
            Node waiteNode = addConditionWaiter();

            /*
             *  针对独占锁，丢弃Node所在线程的持有的所有【许可证】数量由savedState保存
             *  并唤醒[同步队列]排在首位的线程，这样又可以去抢占锁
             */
            int savedState = fullyRelease(waiteNode);

            int interruptMode = 0;

            /*
             *  判断Node 是否位于[同步队列]中重新获取锁
             */
            while (!isOnSyncQueue(waiteNode)) {

                //超时
                if (nanosTimeout <= 0L) {
                    // 立即将【|条件队列|】中的node状态码更新为0，并追加到【|同步队列|】
                    transferAfterCancelledWait(waiteNode);
                    break;
                }
                // 如果时间过短，就不阻塞了，一直循环，直到超时
                if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD) {
                    // 使线程阻塞nanosTimeout（单位：纳秒）时长后自动醒来（中途可被唤醒）
                    LockSupport.parkNanos(this, nanosTimeout);
                }

                /*
                 *  从这里被 1: signal() 唤醒以后，
                 *      Node 节点已经成为了【同步节点】的首个节点 (不是头节点)
                 *        此时while循环就进不来了，该线程可以去抢锁了
                 *
                 *       2: 当然，这里也有可能是超时后自然醒来的
                 *        如果该线程是超时后自己醒来的，则会将自身追加到【|同步队列|】并跳出循环
                 */

                // 线程醒来后，首先检查其当前是否有中断标记，如果有的话直接跳出循环
                if ((interruptMode = checkInterruptWhileWaiting(waiteNode)) != 0) {
                    break;
                }

                // 判断是否超时（因为可能是半道被唤醒的）
                nanosTimeout = deadTime - System.nanoTime();

            }

            /*
             * 之前被阻塞的线程现在已经可以去争锁了
             * 而且，争锁时会携带之前保存的许可证数量
             * 争锁成功后，该结点会成为【|同步队列|】的头结点，并恢复运行
             */
            if (acquireQueued(waiteNode, savedState)) {

                // 如果不需要抛异常，则修改标记为REINTERRUPT，代表稍后要恢复线程的中断状态
                if (interruptMode != THROW_IE) {
                    interruptMode = REINTERRUPT;
                }
            }

            if (waiteNode.nextWaiter != null) {
                unlinkCancelledWaiters();
            }

            // 有中断标记的情况下
            if (interruptMode != 0) {
                // 对刚刚醒来的带有中断标记的线程进行特殊处理
                reportInterruptAfterWait(interruptMode);
            }

            // 计算残留的时间，小心溢出（如果是自然醒来，此处为负，如果是中途被唤醒，此处可能为正）
            long remaining = deadTime - System.nanoTime(); // avoid overflow

            return (remaining <= initialNanos) ? remaining : Long.MIN_VALUE;

        }

        @Override
        public void awaitNanos(long nanosTimeout, TimeUnit unit) throws InterruptedException {

        }

        @Override
        public boolean awaitUntil(Date deadline) throws InterruptedException {
            return false;
        }

        /*
         * 将【条件队列】中的首节点追加到【同步队列】 并让其处于待唤醒中
         */
        @Override
        public final void signal() {

            //不是自身的线程
            if (!isHeldExclusively()) {
                throw new IllegalMonitorStateException();
            }

            Node first = firstWaiter;
            if (first != null) {
                doSignal(first);
            }

        }

        @Override
        public void signalAll() {

        }

        /*
         * 将条件队列中的首节点放入到【同步队列】中,并设置为待唤醒的状态
         */
        private void doSignal(Node node) {

            do {
                //从队列中删除首节点
                if ((firstWaiter = node.nextWaiter) == null) {
                    lastwaiter = null;
                }
                // 切断首结点与后续结点的关联
                node.nextWaiter = null;

                /*
                 * 尝试将node状态码更新为0，并追加到【|同步队列|】，并为其前驱设置Node.SIGNAL标记
                 *  如果更新状态码时就失败了，需要摘取【|条件队列|】的下一个结点继续尝试
                 *
                 */
            } while (!transferForSignal(node) && (node = firstWaiter) != null);

        }

        /*
         * 添加一个新的[条件Node] 到 条件队列中排队，该Node缓存了对当前线程的引用
         * 添加完成后，返回该Node
         * 条件队列
         * <p>
         * Node --nextWaiter--> Node ----> Node -----> Node
         * firstWaiter                                 lastWaiter
         */
        private Node addConditionWaiter() {

            // 判断当前线程不是锁的持有者，报错
            if (!isHeldExclusively()) {
                throw new IllegalMonitorStateException();
            }

            Node t = lastwaiter;

            // 这里做一些判断逻辑
            if (t != null && t.waitStatus != Node.CONDITION) {
                // 移除已经取消的等待节点
                unlinkCancelledWaiters();
                t = lastwaiter;
            }

            //创建一个带有 条件表识【Node.CONDITION】的节点
            Node node = new Node(Node.CONDITION);

            if (t == null) {
                firstWaiter = node;
            } else {
                t.nextWaiter = node;
            }

            lastwaiter = node;

            return node;

        }

        /*
         * 从[条件队列]中移除已取消的节点
         * nextWaiter
         * * Node ----> Node ----> Node -----> Node
         * * firstWaiter                                 lastWaiter
         * trail
         */
        private void unlinkCancelledWaiters() {

            //因为是单向列表，所以需要从头开始遍历
            Node t = firstWaiter;
            Node trail = null;

            while (t != null) {

                Node nextWaiter = t.nextWaiter;
                if (t.waitStatus != Node.CONDITION) {
                    t.nextWaiter = null;
                    //表示头节点出问题
                    if (trail == null) {
                        // 移动头指针
                        firstWaiter = nextWaiter;
                    } else {
                        trail.nextWaiter = nextWaiter;
                    }
                    //走到最后
                    if (nextWaiter == null) {
                        lastwaiter = trail;
                    }
                } else {
                    trail = t;
                }
                t = nextWaiter;
            }

        }

        /*
         * 尝试将【|条件队列|】中的node状态码更新为0，并追加到【|同步队列|】
         */
        final boolean transferAfterCancelledWait(Node node) {

            //尝试将【|条件队列|】中的node状态码更新为0
            if (node.compareAndSetWaitStatus(Node.CONDITION, 0)) {
                //使用尾插法讲Node 放入【同步队列】
                enq(node);
                return true;
            }
            //当不在【同步队列】中的时候，让出cpu使用权，大家重新获取
            while (!isOnSyncQueue(node)) {
                Thread.yield();
            }

            return false;
        }

        /*
         * 检查当前线程是否有中断标记，并清除中断标记
         *
         * 返回0：无中断标记
         * 返回THROW_IE(-1)：有中断标记，且node成功加入到了【|同步队列|】末尾
         * 返回REINTERRUPT(1)：有中断标记，node还在【|条件队列|】中
         */
        private int checkInterruptWhileWaiting(Node node) {

            return Thread.interrupted() ? (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 0;
        }

        /*
         * 对刚刚唤醒的带有中断标记的线程进行特殊处理
         */
        private void reportInterruptAfterWait(int interruptMode) throws InterruptedException {
            // 如果该线程已经在【|同步队列|】，则抛出异常
            if (interruptMode == THROW_IE) {
                throw new InterruptedException();
            } else if (interruptMode == REINTERRUPT) {
                // 否则，说明该线程node仍在【|条件队列|】，此时需要为线程恢复中断标记 --超时醒来
                selfInterrupt();
            }
        }
    }

    /*
     * 针对独占锁，丢弃node所在线程持有的所有许可证，并唤醒【|同步队列|】后续的阻塞线程
     */
    final int fullyRelease(Node node) {

        try {
            //获取当前线程锁持有的许可证
            int savedState = getState();
            // 尝试完全释放锁，并唤醒后续的阻塞线程。返回值表示本次操作后锁是否自由
            boolean release = release(savedState);
            if (release) {
                // 返回释放前的许可证数量
                return savedState;
            }
            throw new IllegalMonitorStateException();
        } catch (Throwable t) {
            node.waitStatus = Node.CANCELLED;
            throw t;
        }
    }

    /*
     * 如果节点（最初放置在条件队列中）现在正位于同步队列中等待重新获取锁，则返回true
     */
    final boolean isOnSyncQueue(Node node) {

        if (node.waitStatus == Node.CONDITION || node.prev == null) {
            //位于条件队列中
            return false;
        }
        // If has successor, it must be on queue
        if (node.next != null) {
            // 位于同步队列中
            return true;
        }

        return findNodeFromTail(node);
    }

    /*
     * 从【|同步队列|】队尾出发，向前查找node
     */
    private boolean findNodeFromTail(Node node) {

        for (Node p = tail; ; ) {

            if (p == node) {
                return true;
            }
            if (p == null) {
                return false;
            }
            p = p.prev;
        }
    }

    /*
     * 尝试将Node.waitStatus 设置为0，并且添加到[同步队列]中,并且
     * 设置其前驱节点为Node.Singal状态
     */
    final boolean transferForSignal(Node node) {

        //cas 交换状态
        if (!node.compareAndSetWaitStatus(node.CONDITION, 0)) {
            return false;
        }

        // 尾插进入 [同步队列] 返回老的尾节点
        Node oldTail = enq(node);
        int ws = oldTail.waitStatus;

        //设置失败，唤醒当前节点线程
        if (ws > 0 || !oldTail.compareAndSetWaitStatus(ws, Node.SIGNAL)) {
            LockSupport.unpark(node.thread);
        }


        return true;
    }


}